package com.mengfou.binarysearch;

/**
 * @author mengfou
 */
public class FindLocalMaximumValue {

    public static void main(String[] args) {
        int[] arr = new int[]{2, 3, 5, 7, 9, 11};
        int i = new FindLocalMaximumValue().localMaximum(arr);
        System.out.println(i);
    }

    /**
     * 查找数组中的局部最大值
     * @param arr 待查找数组
     * @return 局部最大值
     */
    public int localMaximum(int[] arr){
        int len = 0;
        if (arr == null || (len = arr.length) == 0 || len < 2) return -1;

        // 首尾边界情况
        if (arr[0] > arr[1]) return 0;
        if (arr[len - 1] > arr[len - 2]) return len - 1;

        // 其余情况
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (mid >= 1 && mid < len - 1 &&
                    arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1]) { // 当前满足局部最大值
                return mid;
            } else if (mid >= 1 && arr[mid] < arr[mid - 1]) { // 局部最大值在左侧
                right = mid - 1;
            } else if (mid < len - 1 && arr[mid] < arr[mid + 1]) { // 局部最大值在右侧
                left = mid + 1;
            }
        }
        return -1;
    }
}
